package org.alis.smallcc.algorithm;

import java.util.Set;


import com.google.common.collect.Sets;

/**
 * 老鼠喝药的问题
 * 
 * 如果有 1000个瓶 999瓶是水 1瓶是毒药 毒发作是1分钟 请在一分钟后找出毒瓶
 * 
 * 延伸 如果给你2分钟找出来 第一次死了的不能用在第二次实验 你至少需要几只
 * 
 * @author luochuan
 */
public class Mouse {

	public static void main(String[] args) {
		Integer bottleSize = 1000;
		System.out.println(isSatisfy(10, 1000));
		
		System.out.println(getBottle(10,1000,Sets.newHashSet(0,1,2,3,4,5,6,7,9)));
		
		
		System.out.println("多少只老鼠:"+getNeedMouse(bottleSize));
		
		
	}

	/**
	 * 首先需要一个判断函数就是 一次实验瓶子和老鼠的关系 分析算法 这个是求一个O(1)的最有解的过程 既然是O(1)那么空间复杂度至少是f(n) 1.假设
	 * n只老鼠能得确定1瓶毒药 就得出f(n)的关系 那么 n只老鼠每个老鼠各自喝一瓶则有 C(n,1) 2.由1基础知之上两两组合就得到C(n,2)
	 * 3.以此类推 老鼠的组合关系是 n个老鼠n个组合得到c(n,n)瓶 4.f(n)=c(n,1)+c(n,2)+c(n,n)=2^n 得到
	 * 2^n可以得到最多确定的瓶子数
	 * 
	 * @param mouseSize  老鼠数量
	 * @param bottleSize 瓶子数
	 * @return 是否可以计算出来
	 */
	private static boolean isSatisfy(Integer mouseSize, Integer bottleSize) {
		double pow = Math.pow(2d, mouseSize);
		return pow >= bottleSize;
	}
	
	/**
	 * 扩展如果一个老鼠只能实验两瓶那么只要排列组合的最后结果为一只老鼠 就能找到中间过程
	 * 瓶子数
	 */
	private static Integer getNeedMouse(Integer bottleSize) {
		int count = 0;
		while(bottleSize>=2) {
			bottleSize= (int) Math.ceil((double)bottleSize/2);
			count++;
		}
		return count;
		
	}

	/**
	 * 由{@link org.alis.smallcc.algorithm.Mouse#isSatisfy(Integer mouseSize,Integer bottleSize)}得到的结论是
	 * 1000个瓶子可以转换成 4个瓶子和 2个老鼠
	 * 
	 * 首先将 4 瓶药以二进制形式排序。 00 // 药1 01 // 药2 10 // 药3 11 // 药4 因为 4 瓶药用 2
	 * 位的二进制就能表示了，所以我们只需要 2 只老鼠就能试出毒来了。 每只老鼠对应二进制的一位，且 喝位数为 1 所在药水的混合药水；
	 * 比如上面的例子里第一只老鼠对应 0011,那么喝 3 号、4 号药水的混合药水； 另一只对应 0101，那么喝 2 号和 4 号药水的混合药水；
	 * 这样对应也会出现 4 种情况： 
	 * 活活（都没喝 1 号药水，1 号药水是毒药）
	 * 活死（只有 2 号喝了 2 号药水，2 号药水是毒药）
	 * 死活（只有 1号喝了 3 号药水，3 号药水是毒药）
	 * 死死（都喝了 4 号药水，4 号药水是毒药）
	 *
	 * 获取毒瓶编号
	 * 
	 * @param mouseSize  老鼠数量
	 * @param bottleSize 瓶子数
	 * @param delMouse   死亡老鼠
	 * @return 毒瓶编号
	 */
	private static Integer getBottle(Integer mouseSize, Integer bottleSize, Set<Integer> delMouse) {
		if (!isSatisfy(mouseSize, bottleSize)) {
			System.out.println("理论得出该实验无法进行");
			return -1;
		}
		StringBuilder bin = new StringBuilder();
		for(int i=mouseSize-1;i>=0;i--) {
			bin.append(delMouse.contains(i)?"1":"0");
		}
		Integer num = Integer.valueOf(bin.toString(),2);
		System.out.println("得到的瓶子的排序号是:"+bin.toString());
		System.out.println("瓶子的编号是:"+num);
		return num;
	}
	/**
	 * 扩展如果给你2分钟找出来 第一次死了的不能用在第二次实验 你至少需要几只
	 * 其实很简单 两两组合变成了三三组合而已
	 * 算法就得到 f(n)=(t+1)^n
	 */
	
	

}
